#include <iostream>
#include <fstream>
#include <sstream>
#include <cstdlib>
#include <string>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <list>
#include <cassert>
#include <utility>

using namespace std;

const unsigned int ASCII_A = 97;
const unsigned int ASCII_Z = ASCII_A + 26;
const bool         __DEBUG = false;

typedef size_t etat_t;
typedef unsigned char symb_t;
typedef set<etat_t > etatset_t;
typedef vector<vector<etatset_t > > trans_t;
typedef vector<etatset_t > epsilon_t;
typedef map<etatset_t, etat_t > map_t;

template<class T> ostream& operator<<(ostream& out, const set<T>& s);
ostream& operator<<(ostream& out, const trans_t& s);
ostream& operator<<(ostream& out, const epsilon_t& etats);

/*!
 * \brief Répresente un automate finit non deterministe avec epsilon transition
 */
class AutoNDE{

private:
    /*!
     * \brief nb_etats Nombre d'état
     */
    size_t nb_etats;
    /*!
     * \brief nb_symbs Nombre de symboles acceptés
     */
    size_t nb_symbs;
    /*!
     * \brief nb_finaux Nombre d'états finaux
     */
    size_t nb_finaux;
    /*!
     * \brief initial Numéro de l'état initial
     */
    etat_t initial;
    /*!
     * \brief finaux Ensemble de numéro des états finaux
     */
    etatset_t finaux;
    /*!
     * \brief trans Matrice de transition qui pour chaque etat et chaque symbole associe un ensemble d'état de destination
     */
    trans_t trans;
    /*!
     * \brief epsilon Matrice de transitions spontanées qui pour chaque état associe un ensemble d'état de destination accéssible par epsilon transition
     */
    epsilon_t epsilon;
    /*!
    * \brief frermeture transitive de epsilon.
    */
    epsilon_t epsilon_clot;

    AutoNDE(const AutoNDE&); /*Interdiction de l'affectation par l'opérateur de recopie = en dehors de la classe*/

public:
    AutoNDE();
    AutoNDE(const string& filename);

    static AutoNDE* FromFile(string path);

    bool ContientFinal(const etatset_t& e) const;
    void Fermeture(etatset_t& e);
    bool EstDeterministe() const;
    void Warshall();
    etatset_t Delta(const etatset_t& e, symb_t c);
    bool Accept(string str);

    bool ToGraph(string path);
    pair<AutoNDE* ,map_t> Determinize();

    AutoNDE* Append(const AutoNDE& value) const;
    AutoNDE* Union(const AutoNDE& value) const;
    AutoNDE* Concat(const AutoNDE& value) const;
    AutoNDE* Complement() const;
    AutoNDE* Kleene() const;
    AutoNDE* Intersection(const AutoNDE& value) const;

    friend ostream& operator<<(ostream& out, const AutoNDE& value);
    friend istream& operator>>(istream& in, AutoNDE& value);
};
